package com.singzi.leetcode.N100;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 *
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 * 示例 2：
 *
 * 输入：nums = [0]
 * 输出：[[],[0]]
 *
 */
public class T0046 {
    public static void main(String[] args) {
        Solution0046 solution0046 = new Solution0046();
        int []a = {1,2,3};
        System.out.println(solution0046.permute(a));
    }
}
class Solution0046 {
    public List<List<Integer>> permute(int[] nums) {

        ArrayList temp = new ArrayList();
        int[] visited = new int[nums.length];//标记已经进入temp的i
        backTrace(temp,nums,visited);
        return list;

    }
    ArrayList list = new ArrayList();
    public void backTrace(List<Integer> temp,int[] nums,int[] visited){
        if(temp.size()==nums.length){
            list.add(new ArrayList<>(temp));
            return;
        }
        HashSet<Integer>[]set = new HashSet[2];
        for(int i = 0;i<nums.length;i++){
            if (visited[i] == 1)
                continue;
            visited[i] = 1;
            temp.add(nums[i]);
            backTrace(temp,nums, visited);
            visited[i] = 0;
            temp.remove(temp.size() - 1);
        }
    }
}